/* 本题要求实现一个函数，将两个链表表示的递增整数序列合并成为一个
 * 非递减的整数序列
 * 函数接口定义：
 * List Merge(List L1, List L2)
 * L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；
 * 函数Merge要将L1和L2合并成为一个非递减的整数序列。应直接使用原
 * 序列中的结点，返回归并后的链表头指针。
 */


#include <stdio.h>
#include <stdlib.h>

/* List结构定义 */
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode List;

/* 读取列表存入List */
List Read();

/* 按顺序打印列表 */
void Print(List L);

/* 合并两个链表 */
List Merge(List L1, List L2);

/* 主函数 */
int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* =================================================================== 
 * 以上各接口实现 
 * ===================================================================
 */

/* 读入数据保存至一个带头结点的链表 */
List Read()
{
    List PtrL, TmpL;
    int N, i, elem;
    scanf("%d", &N);
    PtrL = (List)malloc(sizeof(struct Node));
    TmpL = PtrL;
    for (i = 0; i < N; i++) {
        scanf("%d", &elem);
        TmpL->Next = (List)malloc(sizeof(struct Node));
        TmpL->Next->Data = elem;
        TmpL = TmpL->Next;
    }
    TmpL->Next = NULL;
    return PtrL;
}

/* 按顺序打印列表 */
void Print(List L)
{
    List PtrL = L->Next;
    int flag = 0;
    if (PtrL) {
        while (PtrL) {
            if (flag == 0) {
                printf("%d", PtrL->Data);
                PtrL = PtrL->Next;
                flag = 1;
            }
            if (flag) {
                printf(" %d", PtrL->Data);
                PtrL = PtrL->Next;
            }
        }
        printf("\n");
    }
    else
        printf("NULL\n");
}

/* 将L1和L2合并为一个非递减的整数序列 */
List Merge(List L1, List L2)
{
    List L, p1, p2, tmp;
    // L指向最终合并的链表
    L = (List)malloc(sizeof(struct Node));
    int flag = 0;
    p1 = L1->Next;
    p2 = L2->Next;
    while (p1 && p2) {
        // 确定L的第一个结点是属于L1还是L2
        if (flag == 0) {
            if (p1->Data <= p2->Data) {
                L->Next = p1;
                flag = 1;
            } else {
                L->Next = p2;
                flag = 1;
            }
        } else {
            if (p1->Data <= p2->Data) {
                // 如果p1->Data <= p2->Data，则p1继续向下移动，直到
                // p1->Data > p2->Data 或 p1 == NULL 停止
                while (p1->Data <= p2->Data) {
                    tmp = p1;
                    p1 = p1->Next;
                    if (!p1) break;
                }
                // p1==NULL说明L1遍历完毕，跳出循环后把L2剩下的元素
                // 连接到p1后面，此时tmp保存着上一个p1值
                if (!p1) break;
                tmp->Next = p2;
                p2 = p2->Next;
                tmp->Next->Next = p1;
            } else {
                while (p1->Data >= p2->Data) {
                    tmp = p2;
                    p2 = p2->Next;
                    if (!p2) break;
                }
                if (!p2) break;
                tmp->Next = p1;
                p1 = p1->Next;
                tmp->Next->Next = p2;
            }
        }
    }
    if (p1) tmp->Next = p1; // 把p1剩下的元素接到合并链表后面
    if (p2) tmp->Next = p2; // 把p2剩下的元素接到合并链表后面
    // 把L1和L2置为NULL
    L1->Next = NULL;
    L2->Next = NULL;
    return L;
}
